package algorithm.dfs;


import java.util.Stack;

/**
 * 输入两个整数n和m,从数列1,2,3....n中随意取几个数,使其和等于m
 * ,要求将所有结果列出来
 *
 * 这道题用dfs+回溯逐个遍历结果集
 *
 * @author shenenlu 2021年05月03日 上午02:50:43
 */
public class DfsSum {

    private Stack<Integer> stack;

//    private static Stack<Integer> stack = new Stack<>();

    private int n;

    private int m;

    public DfsSum(int n, int m) {
        stack = new Stack<>();
        this.n = n;
        this.m = m;
    }

    void dfs(int index, int sum){
//        stack.forEach(r-> System.out.print(r + " "));
//        System.out.println();
        System.out.println("index="+index +" sum=" + sum);
        if( sum > m ){
            return;
        }
        if( sum == m ){
//            stack.forEach(r-> System.out.print(r + " "));
//            System.out.println();
        }else{
            for(int j=index; j<=n ; j++){
//            for(int j=index; j<=n && sum < m && j <= m ; j++){//sum<m&&j<=m对树进行剪枝
                stack.push(j);
                System.out.println("index="+index + " j="+ j+" sum=" + sum);
                dfs(j + 1,sum + j);
                stack.pop();//凑够了就弹出，没凑够说明加上这个数不可能凑够，所以也弹出
            }
        }
    }


//    static void dfs(int index, int sum, int n, int m ){
//        System.out.println(index+ " " +sum);
//        if( sum > m ){
//            return;
//        }
//        if( sum == m ){
////            stack.forEach(r-> System.out.print(r + " "));
////            System.out.println();
//        }else{
//            for(int j=index; j <= n  ; j++){//sum <m && j<= m对树进行剪枝
//                stack.push(j);
//                dfs(j + 1,sum + j, n, m);
//                stack.pop();//凑够了就弹出，没凑够说明加上这个数不可能凑够，所以也弹出
//            }
//        }
//    }


    public static void main(String[] args) {
        DfsSum dfsSum = new DfsSum(4,50);
        dfsSum.dfs(1,0);
//        dfs(1,0, 3, 3);


    }

}
